package com.datastructure.test.longestcommonchildserial;

public class LongestCommonChildSerial {

    public static void main(String[] args) {
        LongestCommonChildSerial longestCommonChildSerial = new LongestCommonChildSerial();
        int lcs = longestCommonChildSerial.LCS("abc", "xyz");
        System.out.println(lcs);
    }

    public int LCS (String s1, String s2) {
        // write code here
        byte[] s1Bytes = s1.getBytes();
        byte[] s2Bytes = s2.getBytes();
        int s1OfLength = s1Bytes.length;
        int s2OfLength = s2Bytes.length;
        int[][] temp = new int[s1OfLength +1][s2OfLength +1];
        for (int i = 1; i <= s1OfLength; i++) {
            for (int j = 1; j <= s2OfLength; j++) {
                if(s1Bytes[i-1]==s2Bytes[j-1]){
                    temp[i][j]=temp[i-1][j-1]+1;
                } else {
                    temp[i][j]=Math.max(temp[i-1][j],temp[i][j-1]);
                }
            }
        }
        return temp[s1OfLength][s2OfLength];
    }
}
